home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / unix / volume18 / mcqueer-lib < prev    next >
Encoding:
Text File  |  1989-11-09  |  26.8 KB  |  1,164 lines

  1. Article 313 of comp.sources.unix:
  2. From: rsalz@uunet.uu.net (Rich Salz)
  3. Newsgroups: comp.sources.unix
  4. Subject: v18i054:  Library for hat/coat and others
  5. Approved: rsalz@uunet.UU.NET
  6.  
  7. Submitted-by: Bob McQueer <mtxinu!rtech!weevil!bobm@uunet.uu.net>
  8. Posting-number: Volume 18, Issue 54
  9. Archive-name: mcqueer-lib
  10.  
  11. [  I don't want to get into the practice of posting everyone's favorite
  12.    toolkit/library...  --r$  ]
  13.  
  14. This is a small set of utilities for generic use, at least in bobm
  15. generated programs.
  16.  
  17. ----------
  18. #! /bin/sh
  19. # This is a shell archive, meaning:
  20. # 1. Remove everything above the #! /bin/sh line.
  21. # 2. Save the resulting text in a file.
  22. # 3. Execute the file with /bin/sh (not csh) to create:
  23. #    README
  24. #    Makefile
  25. #    diagnostic.c
  26. #    hash.c
  27. #    prime.c
  28. #    strstore.c
  29. #    strtok.c
  30. export PATH; PATH=/bin:/usr/bin:$PATH
  31. echo shar: "extracting 'README'" '(637 characters)'
  32. if test -f 'README'
  33. then
  34.     echo shar: "will not over-write existing file 'README'"
  35. else
  36. cat << \SHAR_EOF > 'README'
  37. This is a small set of utilities for generic use, at least in bobm
  38. generated programs:
  39.  
  40.     hash.c, prime.c - manage hash tables.
  41.     strstore.c - store and free copies of strings.
  42.     diagnostic.c - produce diagnostic & fatal error messages.
  43.  
  44. read comments in the individual sources for directions on using them.
  45.  
  46. strtok.c is also contained herein.  If you are SYSV, or any other system
  47. which has that in the runtime library, remove it from the makefile.
  48.  
  49. Before you build, fill in the makefile to put the results where you want them.
  50.  
  51. hash.c and str_store.c manage dynamic memory.  #define's in those files
  52. control allocation block sizes, etc.
  53. SHAR_EOF
  54. fi
  55. echo shar: "extracting 'Makefile'" '(810 characters)'
  56. if test -f 'Makefile'
  57. then
  58.     echo shar: "will not over-write existing file 'Makefile'"
  59. else
  60. cat << \SHAR_EOF > 'Makefile'
  61. #
  62. # where to put the library
  63. #
  64. LIBARC = $(HOME)/lib/bobm.a
  65.  
  66. # if your compiler doesn't like the initialization of a pointer with
  67. # an array address in strstore.c, define NO_PTR_INIT
  68. #
  69. # if you define HASHMAGIC to be some number, you will get magic number
  70. # checks in the hash table routines, which can be helpful in tracking
  71. # down instances of client code passing bad context addresses.  Not done
  72. # by default to avoid overhead.  See hash.c
  73. #
  74. CFLAGS = -O
  75.  
  76. #
  77. # if strtok() is available in your c runtime library, remove it from
  78. # the list - this will be all SYSV, and some BSD systems like ULTRIX
  79. #
  80. LIBOBJS = hash.o diagnostic.o prime.o strstore.o strtok.o
  81.  
  82. #
  83. # for SYSV, make RANLIB an effective no-op, like "ls" or "echo"
  84. #
  85. RANLIB = ranlib
  86.  
  87. lib : $(LIBOBJS)
  88.     ar rvu $(LIBARC) $(LIBOBJS)
  89.     $(RANLIB) $(LIBARC)
  90. SHAR_EOF
  91. fi
  92. echo shar: "extracting 'diagnostic.c'" '(1977 characters)'
  93. if test -f 'diagnostic.c'
  94. then
  95.     echo shar: "will not over-write existing file 'diagnostic.c'"
  96. else
  97. cat << \SHAR_EOF > 'diagnostic.c'
  98. #include <stdio.h>
  99.  
  100. /*
  101. ** generic error message routines.  Diag_xxx, may be externally set by caller.
  102. **
  103. ** possible portability problem - use of several "long" arguments to pass
  104. ** stack through to underlying printf() family routine.
  105. */
  106.  
  107. /*
  108. **
  109. **    Copyright (c) 1987, Robert L. McQueer
  110. **        All Rights Reserved
  111. **
  112. ** Permission granted for use, modification and redistribution of this
  113. ** software provided that no use is made for commercial gain without the
  114. ** written consent of the author, that all copyright notices remain intact,
  115. ** and that all changes are clearly documented.  No warranty of any kind
  116. ** concerning any use which may be made of this software is offered or implied.
  117. **
  118. */
  119.  
  120. char *Diag_file = "";        /* filename for use in diagnostic message */
  121. int Diag_line = 1;        /* diagnostic line number */
  122. int Diag_count = 0;        /* diagnostic counter */
  123. FILE *Diag_fp = stderr;        /* output stream for messages */
  124. char *Diag_cmd = "?";        /* command name for fatal() / usage() */
  125.  
  126. static int (*Fatcall)() = NULL;
  127.  
  128. /*
  129. ** print nonfatal diagnostic with line number from an input file.  Format
  130. ** compatible with "context"
  131. */
  132. diagnostic(s,a,b,c,d,e,f)
  133. char *s;
  134. long a,b,c,d,e,f;
  135. {
  136.     fprintf(Diag_fp,"%s line %d: ",Diag_file,Diag_line);
  137.     fprintf(Diag_fp,s,a,b,c,d,e,f);
  138.     fprintf(Diag_fp,"\n");
  139.     ++Diag_count;
  140. }
  141.  
  142. /*
  143. ** print fatal error message and exit.  May call user set cleanup routine first.
  144. ** argument list passed to fatal() will also be passed to cleanup routine.
  145. */
  146. fatal (s,a,b,c,d,e,f)
  147. char *s;
  148. long a,b,c,d,e,f;
  149. {
  150.     fprintf (Diag_fp,"%s: ",Diag_cmd);
  151.     fprintf (Diag_fp,s,a,b,c,d,e,f);
  152.     fprintf (Diag_fp,"\n");
  153.     if (Fatcall != NULL)
  154.         (*Fatcall) (s,a,b,c,d,e,f);
  155.     exit (1);
  156. }
  157.  
  158. /*
  159. ** set cleanup routine for fatal() calls
  160. */
  161. fat_set (fn)
  162. int (*fn) ();
  163. {
  164.     Fatcall = fn;
  165. }
  166.  
  167. /*
  168. ** print usage message and exit.
  169. */
  170. usage (s,a,b,c,d,e,f)
  171. char *s;
  172. long a,b,c,d,e,f;
  173. {
  174.     fprintf (Diag_fp,"usage: %s ",Diag_cmd);
  175.     fprintf (Diag_fp,s,a,b,c,d,e,f);
  176.     fprintf (Diag_fp,"\n");
  177.     exit (1);
  178. }
  179. SHAR_EOF
  180. fi
  181. echo shar: "extracting 'hash.c'" '(11529 characters)'
  182. if test -f 'hash.c'
  183. then
  184.     echo shar: "will not over-write existing file 'hash.c'"
  185. else
  186. cat << \SHAR_EOF > 'hash.c'
  187. #include <stdio.h>
  188.  
  189. /*
  190. **
  191. **    Copyright (c) 1987, Robert L. McQueer
  192. **        All Rights Reserved
  193. **
  194. ** Permission granted for use, modification and redistribution of this
  195. ** software provided that no use is made for commercial gain without the
  196. ** written consent of the author, that all copyright notices remain intact,
  197. ** and that all changes are clearly documented.  No warranty of any kind
  198. ** concerning any use which may be made of this software is offered or implied.
  199. **
  200. */
  201.  
  202. /*
  203. ** generic hash table routines.
  204. **
  205. **    htab_init - initialize a new hash table
  206. **    htab_free - destroy a hash table, freeing associated memory
  207. **    htab_clear - remove all hash table entries
  208. **    htab_find - find entry
  209. **    htab_del - delete entry
  210. **    htab_enter - enter item into table
  211. **    htab_list - scan hash table entries.
  212. **
  213. ** Multiple hash tables may be used.  Caller may provide key comparison
  214. ** and hash routines, or use defaults.
  215. */
  216.  
  217. /*
  218. ** HASHMAGIC define may be used to compile a version of these routines
  219. ** which will catch bad context blocks passed in by client routines
  220. ** through a magic number check.  If defined, HASHMAGIC should be the
  221. ** actual number to use for a magic number.  Configurable so that you
  222. ** may avoid the overhead of checking it all the time in these routines
  223. ** which may have high entry rates.
  224. */
  225.  
  226. /*
  227. ** allocation: nodes are allocated starting with a block of ALLOCINIT,
  228. ** doubling the size for the next allocation as long as the size is strictly
  229. ** less than ALLOCLIMIT.  If you make ALLOCLIMIT a value encountered by
  230. ** successive doubling of ALLOCINIT, that will be the final size, otherwise the
  231. ** next doubling larger.
  232. **
  233. ** The idea of this stunt is that we don't know whether the caller is going
  234. ** to make a lot of entries, or just a few.  So we start out allocating
  235. ** just a few nodes at a crack, and as the caller makes more and more
  236. ** entries, allocate bigger bunches.  For memory-restrictive environments
  237. ** like MS-DOS, one could set ALLOCLIMIT low & simply pay the penalty for
  238. ** lots of malloc calls.
  239. */
  240. #define ALLOCINIT 25
  241. #define ALLOCLIMIT 800
  242.  
  243. #define MAGCHECK(T,N) if (T->magic != HASHMAGIC) fatal(Merr,N)
  244.  
  245. typedef struct _htab
  246. {
  247.     struct _htab *next;
  248.     char *key;
  249.     char *data;
  250. } HASHTAB;
  251.  
  252. typedef struct _faddr
  253. {
  254.     struct _faddr *next;
  255. } FADDR;
  256.  
  257. /*
  258. ** fpool, tpool - tpool is the pool of available nodes.  Every time
  259. ** a new block is allocated, one FADDR is allocated along with it.
  260. ** The address allocated is coerced into the FADDR and placed on fpool
  261. ** to facilitate freeing.
  262. */
  263.  
  264. typedef struct
  265. {
  266. #ifdef HASHMAGIC
  267.     int magic;
  268. #endif
  269.     HASHTAB **tab;        /* hash table */
  270.     HASHTAB *tpool;        /* available nodes */
  271.     HASHTAB *srch;        /* current search pointer for htab_list */
  272.     FADDR *fpool;        /* alloc pointers for htab_free */
  273.     int (*afail)();        /* allocation error handler */
  274.     int (*compare)();    /* comparison routine */
  275.     int (*hashfunc)();    /* hash function */
  276.     int size;        /* size of table (length of tab item) */
  277.     int ablock;        /* current allocation block size */
  278.     int srchidx;        /* current table index for htab_list */
  279. } CONTEXT;
  280.  
  281. extern char *malloc();
  282.  
  283. #ifdef HASHMAGIC
  284. static char *Merr = "Bad magic number in hash table context block, %s()";
  285. #endif
  286.  
  287. /*
  288. ** free hash table.  tab is pointer returned by htab_init.
  289. */
  290. htab_free(tab)
  291. char *tab;
  292. {
  293.     register FADDR *ptr, *next;
  294.     int i;
  295.     register CONTEXT *cb;
  296.  
  297.     cb = (CONTEXT *) tab;
  298.  
  299. #ifdef HASHMAGIC
  300.     MAGCHECK(cb,"htab_free");
  301.     ++(cb->magic);
  302. #endif
  303.  
  304.     for (ptr = cb->fpool; ptr != NULL; ptr = next)
  305.     {
  306.         next = ptr->next;
  307.         free ((char *) ptr);
  308.     }
  309.  
  310.     free (tab);
  311. }
  312.  
  313. /*
  314. ** remove all hash table entries.  Does not free memory, simply restores
  315. ** empty table, as if one had called htab_delete on all the keys.  tab is
  316. ** pointer returned by htab_init.
  317. */
  318. htab_clear(tab)
  319. char *tab;
  320. {
  321.     register CONTEXT *cb;
  322.     register HASHTAB **tptr;
  323.     register HASHTAB *nptr;
  324.     int i;
  325.  
  326.     cb = (CONTEXT *) tab;
  327.  
  328. #ifdef HASHMAGIC
  329.     MAGCHECK(cb,"htab_clear");
  330. #endif
  331.  
  332.     tptr = cb->tab;
  333.  
  334.     for (i=0; i < cb->size; ++i,++tptr)
  335.     {
  336.         nptr = *tptr;
  337.         if (nptr == NULL)
  338.             continue;
  339.         while (nptr->next != NULL)
  340.             nptr = nptr->next;
  341.         nptr->next = cb->tpool;
  342.         cb->tpool = *tptr;
  343.         *tptr = NULL;
  344.     }
  345.  
  346.     /* force any open htab_list's to return empty */
  347.     cb->srch = NULL;
  348.     cb->srchidx = cb->size;
  349. }
  350.  
  351. /*
  352. ** initialize a hash table.  Returns a pointer to be used with other
  353. ** calls, NULL for failure.
  354. **
  355. ** The hash table will be maintained as a linked list for each node,
  356. ** so any number of entries can be made to it, whatever the value for
  357. ** size (>100% density is perfectly OK).
  358. **
  359. **    size - size of table.  If hfunc is NULL, will be incremented
  360. **        up to a prime size to suit the type of hash function
  361. **        used by default.  Caller may find out the actual size
  362. **        by calling next_prime().
  363. **
  364. **    allocfail - routine to call in case of memory allocation failure.
  365. **        If NULL, allocation failure will make a call to fatal().
  366. **
  367. **    comp - routine used to compare keys.  returns 0 if equal, non-zero
  368. **        otherwise.  If NULL, strcmp() will be used.  Your own will
  369. **        have to be provided if your keys are something other than
  370. **        strings.  These routines will always call this with the
  371. **        comparison key as the first argument, and the one in the
  372. **        table already as a second argument.  This fact is most
  373. **        useful for making comparisons up to the length of the entered
  374. **        key, for instance.
  375. **
  376. **    hfunc - hash function.  called as (*hfunc)(key, size).  size argument
  377. **        may be ignored if function was written for a specific size.
  378. **        Must return an integer between 0 and size-1.  If NULL, the
  379. **        default hash function is the typical "string-divided-modulo
  380. **        -table-size" algorithm.
  381. */
  382. char *
  383. htab_init(size,allocfail,comp,hfunc)
  384. int size;
  385. int (*allocfail)();
  386. int (*comp)();
  387. int (*hfunc)();
  388. {
  389.     int def_afail();
  390.     int strcmp();
  391.     int hash();
  392.     int i;
  393.     CONTEXT *cb;
  394.  
  395.     if (allocfail == NULL)
  396.         allocfail = def_afail;
  397.  
  398.     if (comp == NULL)
  399.         comp = strcmp;
  400.  
  401.     if (hfunc == NULL)
  402.     {
  403.         size = next_prime(size);
  404.         hfunc = hash;
  405.     }
  406.  
  407.     i = sizeof(CONTEXT) + size * sizeof(HASHTAB *);
  408.  
  409.     if ((cb = (CONTEXT *) malloc(i)) == NULL)
  410.     {
  411.         (*allocfail)();
  412.         return (NULL);
  413.     }
  414.  
  415. #ifdef HASHMAGIC
  416.     cb->magic = HASHMAGIC;
  417. #endif
  418.  
  419.     cb->afail = allocfail;
  420.     cb->compare = comp;
  421.     cb->hashfunc = hfunc;
  422.     cb->size = size;
  423.     cb->tab = (HASHTAB **)(cb+1);
  424.  
  425.     for (i=0; i < cb->size; ++i)
  426.         (cb->tab)[i] = NULL;
  427.     cb->tpool = NULL;
  428.     cb->fpool = NULL;
  429.     cb->ablock = ALLOCINIT;
  430.  
  431.     /* safety, in case somebody calls htab_list wrong */
  432.     cb->srch = NULL;
  433.     cb->srchidx = size;
  434.  
  435.     return ((char *) cb);
  436. }
  437.  
  438.  
  439. /*
  440. ** find an entry in hash table.  The pointer returned is NULL for
  441. ** failure, or the data pointer associated with the key in htab_enter.
  442. **
  443. **    tab - table pointer returned by htab_init.
  444. **    s - search key.
  445. */
  446. char *
  447. htab_find(tab,s)
  448. char *tab;
  449. char *s;
  450. {
  451.     register HASHTAB *ptr;
  452.     register CONTEXT *cb;
  453.  
  454.     cb = (CONTEXT *) tab;
  455.  
  456. #ifdef HASHMAGIC
  457.     MAGCHECK(cb,"htab_find");
  458. #endif
  459.  
  460.     for (ptr = (cb->tab)[(*(cb->hashfunc))(s,cb->size)];
  461.                     ptr != NULL; ptr = ptr->next)
  462.     {
  463.         if ((*(cb->compare))(s,ptr->key) == 0)
  464.             return (ptr->data);
  465.     }
  466.  
  467.     return (NULL);
  468. }
  469.  
  470. /*
  471. ** delete a hash table entry.  Returns 0 for success, <0 for no entry.
  472. **
  473. **    tab - table pointer returned by htab_init.
  474. **    s - search key.
  475. */
  476. htab_del(tab,s)
  477. char *tab;
  478. char *s;
  479. {
  480.     register HASHTAB *ptr;
  481.     register CONTEXT *cb;
  482.     register HASHTAB *pred;
  483.     int idx;
  484.  
  485.     cb = (CONTEXT *) tab;
  486.  
  487. #ifdef HASHMAGIC
  488.     MAGCHECK(cb,"htab_del");
  489. #endif
  490.  
  491.     pred = NULL;
  492.     for (ptr = (cb->tab)[idx = (*(cb->hashfunc))(s,cb->size)];
  493.                         ptr != NULL; ptr = ptr->next)
  494.     {
  495.         if ((*(cb->compare))(s,ptr->key) == 0)
  496.             break;
  497.         pred = ptr;
  498.     }
  499.  
  500.     if (ptr == NULL)
  501.         return (-1);
  502.  
  503.     /*
  504.     ** if we're deleting the current search index in the middle
  505.     ** of an htab_list, go to next item.
  506.     */
  507.     if (ptr == cb->srch)
  508.         cb->srch = ptr->next;
  509.  
  510.     if (pred == NULL)
  511.         (cb->tab)[idx] = ptr->next;
  512.     else
  513.         pred->next = ptr->next;
  514.     ptr->next = cb->tpool;
  515.     cb->tpool = ptr;
  516.  
  517.     return (0);
  518. }
  519.  
  520. /*
  521. ** enter new item into hash table:
  522. **
  523. **    tab - table pointer from htab_init.
  524. **    s - key.
  525. **    data - data to associate with key.  In most cases, will probably
  526. **        actually be a pointer to some sort of structure known
  527. **        to the caller.
  528. **
  529. **    both s and data should point to storage valid for the entire life of
  530. **    the table.  htab_enter can not allocate copies of either of these
  531. **    things since it does not know their structure (if you provided 
  532. **    comparison & hash routines, the key may not actually be a string).
  533. **    htab_enter WILL allocate actual table nodes.  Returns 0 for success,
  534. **    -1 for failure.  Failure return is possible only if allocation
  535. **    failure occurs, and was not set up as fatal in htab_init().
  536. */
  537. htab_enter(tab,s,data)
  538. char *tab;
  539. char *s;
  540. char *data;
  541. {
  542.     register HASHTAB *ptr;
  543.     register CONTEXT *cb;
  544.     HASHTAB *get_node();
  545.     int i;
  546.  
  547.     cb = (CONTEXT *) tab;
  548.  
  549. #ifdef HASHMAGIC
  550.     MAGCHECK(cb,"htab_enter");
  551. #endif
  552.  
  553.     if ((ptr = get_node(cb)) == NULL)
  554.         return (-1);
  555.  
  556.     ptr->next = (cb->tab)[i = (*(cb->hashfunc))(s,cb->size)];
  557.     (cb->tab)[i] = ptr;
  558.     ptr->key = s;
  559.     ptr->data = data;
  560.     return (0);
  561. }
  562.  
  563. /*
  564. ** Routine to scan all hash table entries through successive calls.
  565. ** Returns 1 if an entry found, 0 for no more entries.  Will not
  566. ** be returned in any particular order comprehensible to the
  567. ** calling program (hash table order).
  568. **
  569. **    tab - table pointer from htab_init
  570. **    first - 1 to start scan, 0 on succesive calls.
  571. **    data, key - returned data and key.
  572. **
  573. ** Precautions have been taken to allow interleave of this routine with
  574. ** htab_del and htab_clear, but the only interleave that truly makes
  575. ** sense is to selectively htab_del() entries on some basis as they
  576. ** come back from htab_list().  htab_enter()'s in mid list scan may be
  577. ** done, but they may or may not show up on following calls, dependent
  578. ** on where they were entered in relation to the current list pointer.
  579. **
  580. ** This routine sets a global variable on all successful calls:
  581. **
  582. **    int Htab_Index; hash table index entry was found at.
  583. **
  584. ** By examining this while scanning the list of entries, a caller may
  585. ** obtain statistics on table distribution.  The value will increase
  586. ** monotonically as the search proceeds, skipping across indices
  587. ** with no entries.
  588. */
  589.  
  590. int Htab_Index;
  591.  
  592. htab_list(tab,first,data,key)
  593. char *tab;
  594. int first;
  595. char **data;
  596. char **key;
  597. {
  598.     register CONTEXT *cb;
  599.  
  600.     cb = (CONTEXT *) tab;
  601.  
  602. #ifdef HASHMAGIC
  603.     MAGCHECK(cb,"htab_list");
  604. #endif
  605.  
  606.     if (first)
  607.     {
  608.         cb->srch = NULL;
  609.         cb->srchidx = -1;
  610.     }
  611.  
  612.     while (cb->srch == NULL)
  613.     {
  614.         ++(cb->srchidx);
  615.         if (cb->srchidx >= cb->size)
  616.             return (0);
  617.         cb->srch = (cb->tab)[cb->srchidx];
  618.     }
  619.  
  620.     Htab_Index = cb->srchidx;
  621.  
  622.     *data = (cb->srch)->data;
  623.     *key = (cb->srch)->key;
  624.  
  625.     cb->srch = (cb->srch)->next;
  626.     return(1);
  627. }
  628.  
  629. static HASHTAB *
  630. get_node(cb)
  631. CONTEXT *cb;
  632. {
  633.     char *addr;
  634.     HASHTAB *ptr;
  635.     int i;
  636.  
  637.     if (cb->tpool == NULL)
  638.     {
  639.         addr = malloc((cb->ablock)*sizeof(HASHTAB)+sizeof(FADDR));
  640.         if (addr == NULL)
  641.         {
  642.             (*(cb->afail))();
  643.             return (NULL);
  644.         }
  645.  
  646.         ((FADDR *) addr)->next = cb->fpool;
  647.         cb->fpool = (FADDR *) addr;
  648.         addr += sizeof(FADDR);
  649.         cb->tpool = (HASHTAB *) addr;
  650.         for (i=1; i < cb->ablock; ++i)
  651.             (cb->tpool)[i-1].next = cb->tpool + i;
  652.         (cb->tpool)[i-1].next = NULL;
  653.  
  654.         if (cb->ablock < ALLOCLIMIT)
  655.             cb->ablock *= 2;
  656.     }
  657.  
  658.     ptr = cb->tpool;
  659.     cb->tpool = (cb->tpool)->next;
  660.     return (ptr);
  661. }
  662.  
  663. static int
  664. hash(s,size)
  665. register char *s;
  666. int size;
  667. {
  668.     register long rem;
  669.  
  670.     for (rem = 0; *s != '\0'; ++s)
  671.         rem = (rem * 128 + *s) % size;
  672.     return(rem);
  673. }
  674.  
  675. static int
  676. def_afail()
  677. {
  678.     fatal("memory allocation failure in hash table routines");
  679. }
  680. SHAR_EOF
  681. fi
  682. echo shar: "extracting 'prime.c'" '(1566 characters)'
  683. if test -f 'prime.c'
  684. then
  685.     echo shar: "will not over-write existing file 'prime.c'"
  686. else
  687. cat << \SHAR_EOF > 'prime.c'
  688. /*
  689. **
  690. **    Copyright (c) 1987, Robert L. McQueer
  691. **        All Rights Reserved
  692. **
  693. ** Permission granted for use, modification and redistribution of this
  694. ** software provided that no use is made for commercial gain without the
  695. ** written consent of the author, that all copyright notices remain intact,
  696. ** and that all changes are clearly documented.  No warranty of any kind
  697. ** concerning any use which may be made of this software is offered or implied.
  698. **
  699. */
  700.  
  701. /* return smallest prime >= i */
  702. int
  703. next_prime(i)
  704. int i;
  705. {
  706.     if (i <= 2)
  707.         return (2);
  708.     if ((i%2) == 0)
  709.         ++i;
  710.     while (! is_prime(i))
  711.         i += 2;
  712.     return (i);
  713. }
  714.  
  715. /*
  716. ** simply check all factors <= the square root of the number, with
  717. ** a minor wrinkle:
  718. **
  719. ** we split our checks into two separate chains which cover all
  720. ** numbers with no factors of 2 or 3, avoiding many of the non-
  721. ** prime factors.  factor1 winds up being all integers = 5 mod 6,
  722. ** factor2 all integers >= 7 which = 1 mod 6.  Anything = 0,2,3 or
  723. ** 4 mod 6 divides by 2 or 3.
  724. **
  725. ** this gives a rather small number of redundant factor checks for
  726. ** reasonable sized arguments (say < 10000).  Only for extremely large
  727. ** numbers would the extra overhead justify a "smarter" algorithm.
  728. **
  729. ** only valid for i >= 2.
  730. */
  731. int
  732. is_prime(i)
  733. int i;
  734. {
  735.     int factor1,factor2;
  736.  
  737.     if (i == 2 || i == 3)
  738.         return(1);
  739.  
  740.     if ((i%3) == 0 || (i%2) == 0)
  741.         return(0);
  742.  
  743.     factor1 = 5;
  744.     factor2 = 7;
  745.     while ((factor1 * factor1) <= i)
  746.     {
  747.         if ((i % factor1) == 0)
  748.             return (0);
  749.         if ((i % factor2) == 0)
  750.             return (0);
  751.         factor1 += 6;
  752.         factor2 += 6;
  753.     }
  754.  
  755.     return (1);
  756. }
  757. SHAR_EOF
  758. fi
  759. echo shar: "extracting 'strstore.c'" '(7804 characters)'
  760. if test -f 'strstore.c'
  761. then
  762.     echo shar: "will not over-write existing file 'strstore.c'"
  763. else
  764. cat << \SHAR_EOF > 'strstore.c'
  765. #include <stdio.h>
  766.  
  767. /*
  768. **
  769. **    Copyright (c) 1987, Robert L. McQueer
  770. **        All Rights Reserved
  771. **
  772. ** Permission granted for use, modification and redistribution of this
  773. ** software provided that no use is made for commercial gain without the
  774. ** written consent of the author, that all copyright notices remain intact,
  775. ** and that all changes are clearly documented.  No warranty of any kind
  776. ** concerning any use which may be made of this software is offered or implied.
  777. **
  778. */
  779.  
  780. /*
  781. ** string storage routines.
  782. **
  783. **    str_store - return an allocated copy of a string
  784. **    str_free - free all the strings
  785. **    str_cnew - make a new context block for separate group of strings
  786. **    str_ccur - return the current context block
  787. **    str_cset - set the context block
  788. **    str_cfree - free a context block
  789. **    str_afail - set allocation failure routine
  790. **
  791. ** Callers who simply need to make a single group of "permanent" strings
  792. ** for the life of their process need only call str_store, without worrying
  793. ** about context pointers.  This will probably be suitable for a lot of
  794. ** applications.  The other routines may be used to create separate groups
  795. ** of strings which may be released individually.  The burden on callers
  796. ** to keep track of current context in these cases is traded off against
  797. ** the simplicity for the other case.
  798. **
  799. ** The intent of these routines is to "micro-allocate" strings into a
  800. ** large block of storage, saving malloc() headers.  If used exclusively
  801. ** to store long strings, it might be inefficient.
  802. */
  803.  
  804. char *malloc();
  805.  
  806. /* actual malloc'ed block will be CH_BLOCK + sizeof(CHAIN) */
  807. #define CH_BLOCK (4096 - sizeof(CHAIN))
  808.  
  809. #define MAGICNUM 0x525
  810.  
  811. typedef struct _chain
  812. {
  813.     struct _chain *next;
  814.     int avail;
  815.     char *store;
  816. } CHAIN;
  817.  
  818. typedef struct
  819. {
  820.     int magic;
  821.     CHAIN *flist;
  822. } CONTEXT;
  823.  
  824. static CONTEXT Cb_def[1] =
  825. {
  826.     { MAGICNUM, NULL }
  827. };
  828.  
  829. /*
  830. ** NO_PTR_INIT may be defined if the compiler barfs on attempts
  831. ** to initialize a pointer with an array name.  If defined, extra
  832. ** checks will be made at routine entry to do the initialization
  833. ** first time through
  834. */
  835. #ifdef NO_PTR_INIT
  836. static CONTEXT *Cb = NULL;
  837. #else
  838. static CONTEXT *Cb = Cb_def;
  839. #endif
  840.  
  841. static def_afail()
  842. {
  843.     fatal ("memory allocation failure in string storage");
  844. }
  845.  
  846. static int (*Afail)() = def_afail;
  847.  
  848. /*
  849. ** str_store: return an allocated copy of a string.
  850. **
  851. **    s - the string to make a copy of.  If NULL, an empty string
  852. **        will be returned.
  853. **
  854. ** NOTE: these strings may not be individually freed.  This routine
  855. ** is intended to save memory used for alloc headers by returning
  856. ** pointers into a large blocks of allocated memory.
  857. **
  858. ** Will return NULL for allocation failure if a non-fatal failure
  859. ** routine has been defined (see str_afail).  The default failure
  860. ** routine calls "fatal" with an error message.  If the failure
  861. ** routine does not return, a NULL return from this routine is
  862. ** impossible.
  863. */
  864.  
  865. char *
  866. str_store(s)
  867. char *s;
  868. {
  869.     int len, av, idx;
  870.     char *rptr;
  871.     CHAIN *fp;
  872.  
  873. #ifdef NO_PTR_INIT
  874.     if (Cb == NULL)
  875.         Cb = Cb_def;
  876. #endif
  877.  
  878.     if (s == NULL)
  879.         s = "";
  880.  
  881.     len = strlen(s) + 1;
  882.  
  883.     /* should return inside loop */
  884.     for (idx = 0; idx < 2; ++idx)
  885.     {
  886.         for (fp = Cb->flist; fp != NULL; fp = fp->next)
  887.         {
  888.             if (fp->avail >= len)
  889.             {
  890.                 strcpy ((rptr = fp->store),s);
  891.                 fp->store += len;
  892.                 fp->avail -= len;
  893.                 return (rptr);
  894.             }
  895.         }
  896.  
  897.         /* alloc new block, let it find it on next iteration */
  898.         if (len > CH_BLOCK)
  899.             av = len;
  900.         else
  901.             av = CH_BLOCK;
  902.         if ((rptr = malloc(av + sizeof(CHAIN))) == NULL)
  903.         {
  904.             (*Afail)();
  905.             return (NULL);
  906.         }
  907.         fp = (CHAIN *) rptr;
  908.         fp->next = Cb->flist;
  909.         Cb->flist = (CHAIN *) fp;
  910.         fp->store = rptr + sizeof(CHAIN);
  911.         fp->avail = av;
  912.     }
  913.  
  914.     /* we're screwed up */
  915.     fatal("str_store: BAD craziness");
  916.     return(NULL);
  917. }
  918.  
  919. /*
  920. ** str_free:
  921. **
  922. **    Free all the strings allocated with str_store.  All of those
  923. **    pointers will no longer be valid.
  924. **
  925. **    If str_cnew / str_cset have been used, this call frees the strings
  926. **    in the current context block.
  927. **
  928. **    str_store calls may still be made after this - you're simply
  929. **    starting over.
  930. */
  931. str_free()
  932. {
  933.     CHAIN *ptr;
  934.  
  935. #ifdef NO_PTR_INIT
  936.     if (Cb == NULL)
  937.         Cb = Cb_def;
  938. #endif
  939.  
  940.     for ( ; Cb->flist != NULL; Cb->flist = ptr)
  941.     {
  942.         ptr = (Cb->flist)->next;
  943.         free ((char *) Cb->flist);
  944.     }
  945. }
  946.  
  947. /*
  948. ** str_cnew:
  949. **
  950. **    Make a new context block for str_store()
  951. **
  952. **    A pointer returned from this routine or str_ccur() is the ONLY
  953. **    valid argument for str_cset.
  954. **
  955. **    In effect what you are doing is declaring a new "pool" for all
  956. **    str_store() calls, probably so you can use str_free() to release
  957. **    groups of strings selectively.
  958. **
  959. **    NOTE: you MUST call str_cset() to actually use this new pool.
  960. **
  961. **    You MUST save this pointer to be able to add more strings to
  962. **    or free the pool.  Any number of str_cnew calls may be made,
  963. **    allowing the caller to have as many "pools" of strings as
  964. **    desired.  It is up to the caller to keep track of the context
  965. **    pointers, and which context block is currently in use.
  966. **
  967. **    NULL will be returned for failure to allocate a new context block.
  968. **    This return is only possible if a non-fatal allocation failure
  969. **    routine has been defined.
  970. */
  971. char *
  972. str_cnew()
  973. {
  974.     CONTEXT *ctx;
  975.  
  976.     /*
  977.     ** this is an inefficient use of malloc, but presumably callers
  978.     ** aren't going to define large numbers of context blocks
  979.     */
  980.     if ((ctx = (CONTEXT *) malloc(sizeof(CONTEXT))) == NULL)
  981.     {
  982.         (*Afail)();
  983.         return (NULL);
  984.     }
  985.  
  986.     ctx->magic = MAGICNUM;
  987.     ctx->flist = NULL;
  988.     return ((char *) ctx);
  989. }
  990.  
  991. /*
  992. ** str_ccur:
  993. **
  994. **    return pointer to context in current use, presumably so
  995. **    you can use str_cset to switch back to it later.
  996. */
  997. char *
  998. str_ccur()
  999. {
  1000. #ifdef NO_PTR_INIT
  1001.     if (Cb == NULL)
  1002.         Cb = Cb_def;
  1003. #endif
  1004.     return ((char *) Cb);
  1005. }
  1006.  
  1007. /*
  1008. ** str_cset:
  1009. **
  1010. **    Set str_store() to a new context block. The ONLY
  1011. **    legitimate argument for this routine is an address returned
  1012. **    from a previous str_cnew() or str_ccur().
  1013. **
  1014. **    All old strings are still valid.  Only str_free returns any
  1015. **    storage.
  1016. **
  1017. **    You may recover the default context prior to any str_cset calls
  1018. **    by setting NULL
  1019. */
  1020. str_cset(ptr)
  1021. char *ptr;
  1022. {
  1023.     if (ptr == NULL)
  1024.         Cb = Cb_def;
  1025.     else
  1026.         Cb = (CONTEXT *) ptr;
  1027.     if (Cb->magic != MAGICNUM)
  1028.         fatal("bad context pointer in str_cset");
  1029. }
  1030.  
  1031. /*
  1032. ** the ONLY legal argument to this routine is pointer returned from
  1033. ** str_cnew.  This routine may be used to indicate that no more strings
  1034. ** are to be allocated on that context block, and the pointer will no
  1035. ** longer be a legal argument to str_cset.  Note that the actual
  1036. ** strings are still allocated, giving you a way to close a pool
  1037. ** while retaining the strings.  If you want to free BOTH the actual
  1038. ** string storage and the pool, you must use str_free first, then
  1039. ** switch context, so that this block is not the current context.
  1040. **
  1041. ** -1 returned for errors - attempts to free the current block or
  1042. ** the default block.
  1043. **
  1044. ** Although the current implementation makes ptr a legal address for
  1045. ** free(), callers should come through this routine instead, to
  1046. ** allow that to change.
  1047. */
  1048. str_cfree(ptr)
  1049. char *ptr;
  1050. {
  1051.     if (ptr == (char *) Cb_def || ptr == (char *) Cb)
  1052.         return (-1);
  1053.  
  1054.     if (((CONTEXT *) ptr)->magic != MAGICNUM)
  1055.         fatal("bad context pointer in str_cfree");
  1056.  
  1057.     /* make it illegal to use freed context block */
  1058.     ((CONTEXT *) ptr)->magic = MAGICNUM + 1;
  1059.  
  1060.     free(ptr);
  1061.     return(0);
  1062. }
  1063.  
  1064. /*
  1065. ** str_afail:
  1066. **
  1067. **    define the routine to be called in the event of an allocation
  1068. **    failure.  By default, fatal() will be called with an error message.
  1069. **    You may reset the default by using NULL.
  1070. **
  1071. **    Returns old failure function to allow resetting.
  1072. */
  1073.  
  1074. typedef int (*FPTR)();    /* needed typedef for Sun compiler */
  1075.  
  1076. FPTR str_afail(func)
  1077. int (*func)();
  1078. {
  1079.     int (*old)();
  1080.  
  1081.     old = Afail;
  1082.     if (func == NULL)
  1083.         Afail = def_afail;
  1084.     Afail = func;
  1085.     return (old);
  1086. }
  1087. SHAR_EOF
  1088. fi
  1089. echo shar: "extracting 'strtok.c'" '(894 characters)'
  1090. if test -f 'strtok.c'
  1091. then
  1092.     echo shar: "will not over-write existing file 'strtok.c'"
  1093. else
  1094. cat << \SHAR_EOF > 'strtok.c'
  1095. #include <stdio.h>
  1096.  
  1097. /*
  1098. ** strtok() is a routine present in SYSV and some BSD runtime libraries.
  1099. ** Use this if it isn't in yours.
  1100. */
  1101.  
  1102. static char *Save=NULL;
  1103.  
  1104. char *index ();
  1105. static char *first_ch (), *last_ch();
  1106.  
  1107. char *
  1108. strtok(str,delim)
  1109. char *str, *delim;
  1110. {
  1111.     register char *tokstart, *tokend;
  1112.  
  1113.     if (str != NULL)
  1114.         Save = str;
  1115.  
  1116.     if (Save == NULL)
  1117.         return (NULL);
  1118.  
  1119.     tokstart = first_ch (Save, delim);
  1120.     tokend = last_ch (tokstart, delim);
  1121.     Save = first_ch (tokend, delim);
  1122.     *tokend = '\0';
  1123.  
  1124.     if (*tokstart == '\0')
  1125.         return (NULL);
  1126.  
  1127.     return (tokstart);
  1128. }
  1129.  
  1130. static char *
  1131. first_ch (str,delim)
  1132. char *str;
  1133. register char *delim;
  1134. {
  1135.     register char *f;
  1136.  
  1137.     for (f = str; *f != '\0' && index(delim,*f) != NULL; ++f)
  1138.         ;
  1139.  
  1140.     return (f);
  1141. }
  1142.  
  1143. static char *
  1144. last_ch (str,delim)
  1145. char *str;
  1146. register char *delim;
  1147. {
  1148.     register char *f;
  1149.  
  1150.     for (f = str; *f != '\0' && index(delim,*f) == NULL; ++f)
  1151.         ;
  1152.  
  1153.     return (f);
  1154. }
  1155. SHAR_EOF
  1156. fi
  1157. exit 0
  1158. #    End of shell archive
  1159.  
  1160. -- 
  1161. Please send comp.sources.unix-related mail to rsalz@uunet.uu.net.
  1162.  
  1163.  
  1164.